package com.hqq.search.union_find;

/**
 * QuickUnion
 * 在QuickFind的基础上进行优化 以树的结构存储节点
 * 每个节点存储的是其父节点 根节点则存储自身
 * 时间复杂度是N
 * Created by heqianqian on 2017/8/2.
 */
public class QuickUnion implements UnionApi {

    private int[] idArray;

    /**
     * 节点个数
     */
    private int count;

    public QuickUnion(int count) {
        this.count = count;
        this.idArray = new int[count];
        for (int i = 0; i < count; i++) {
            idArray[i] = i;
        }
    }

    /**
     * 获得P节点的根节点
     */
    public int root(int p) {
        while (p != idArray[p]) {
            p = idArray[p];
        }
        return p;
    }

    @Override
    public void union(int p, int q) {
        int pRootIndex = root(p);
        int qRootIndex = root(q);
        if (isConnected(p, q)) {
            return;
        }
        idArray[pRootIndex] = idArray[qRootIndex];
        count--;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return root(p) == root(q);
    }

    @Override
    public int find(int p) {
        return idArray[p];
    }

    @Override
    public int count() {
        return this.count;
    }

    @Override
    public int[] getArray() {
        return idArray;
    }
}
